package algorithm;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;


public class LocalAlignment {
	String str1;
	String str2;
	int threshhold;

	ArrayList<entry> opt_matrix;

	ArrayList<entry> sub_matrix;

	File f = new File("out.txt");

	public ArrayList<List> opt_alignments = new ArrayList<List>();
	public ArrayList<List> sub_alignments = new ArrayList<List>();
	public ArrayList<String> opt_alignments_str1 = new ArrayList<String>();
	public ArrayList<String> opt_alignments_str2 = new ArrayList<String>();
	public ArrayList<String> sub_alignments_str1 = new ArrayList<String>();
	public ArrayList<String> sub_alignments_str2 = new ArrayList<String>();




	Hashtable opt_table = new Hashtable();
	Hashtable sub_table = new Hashtable();

	List<Integer> opt_tmplist = new LinkedList<Integer>();
	List<Integer> sub_tmplist = new LinkedList<Integer>();
	String opt_tmp_str1 = "";
	String opt_tmp_str2 = "";
	String sub_tmp_str1 = "";
	String sub_tmp_str2 = "";
	String sign_indel = "_";
	


	public int largest = 0;

	String buf1="";
	String buf2="";

	public String getStr1() {
		return str1;
	}
	public void setStr1(String str1) {
		this.str1 = str1;
	}
	public String getStr2() {
		return str2;
	}
	public void setStr2(String str2) {
		this.str2 = str2;
	}
	public int getThreshhold() {
		return threshhold;
	}
	public void setThreshhold(int threshhold) {
		this.threshhold = threshhold;
	}

	public ArrayList<List> getOpt_alignments() {
		return opt_alignments;
	}
	public ArrayList<List> getSub_alignments() {
		return sub_alignments;
	}

	public Hashtable getOpt_table() {
		return opt_table;
	}
	public Hashtable getSub_table() {
		return sub_table;
	}

	public void opt_alignment()
	{
		opt_matrix = new ArrayList<LocalAlignment.entry>();

		//Init
		for(int i=0;i<(str1.length()+1)*(str2.length()+1);i++)
		{
			opt_matrix.add(new entry());
		}

		//Set 0 to first row
		for (int i=0;i<str1.length()+1;i++){
			opt_mapping(0, i).value=0;
			opt_mapping(0, i).directions.add(direction.begin);
		}

		for( int i=1;i<str2.length()+1;i++){
			opt_mapping(i, 0).value=0;
			opt_mapping(i, 0).directions.add(direction.begin);

			for(int j=1;j<str1.length()+1;j++){
				int l_value=0,u_value=0;

				if (utils.Constant.isAffineGapScore){
					l_value = opt_mapping(i, j-1).value + (useGapExtensionOnThisElement(i, j, direction.left)? utils.Constant.extend : utils.Constant.indel);
					u_value = opt_mapping(i-1, j).value + (useGapExtensionOnThisElement(i, j, direction.up)? utils.Constant.extend : utils.Constant.indel);
				}
				else{
					l_value=opt_mapping(i,j-1).value + utils.Constant.indel;
					u_value=opt_mapping(i-1, j).value + utils.Constant.indel;
				}
				int d_value=opt_mapping(i-1, j-1).value + matchOrNot(i, j);
				int zero_value=0;

				entry e;
				if (utils.Constant.isAffineGapScore){
					e = maxWithAffine(new entry(direction.left, l_value),new entry(direction.up, u_value),
							new entry(direction.diagonal,d_value), new entry(direction.begin, zero_value));
				}
				else
				{
					e = maxWithoutAffine(new entry(direction.left, l_value),new entry(direction.up, u_value),
							new entry(direction.diagonal,d_value), new entry(direction.begin, zero_value));
				}

				opt_mapping(i, j) .directions = e.directions;
				opt_mapping(i, j) .value = e.value;

				largest = largest > e.value? largest:e.value;

			}
		}
	}

	//************************************************************************************************
	//************************************************************************************************
	//suboptimal
	//************************************************************************************************
	//************************************************************************************************	
	public void sub_alignment(){
		sub_matrix = new ArrayList<LocalAlignment.entry>();

		//Init
		for(int i=0;i<(str1.length()+1)*(str2.length()+1);i++)
		{
			sub_matrix.add(new entry());
		}

		//Set 0 to first row
		for (int i=0;i<str1.length()+1;i++){
			sub_mapping(0, i).value=0;
			sub_mapping(0, i).directions.add(direction.begin);
		}

		for( int i=1;i<str2.length()+1;i++){
			sub_mapping(i, 0).value=0;
			sub_mapping(i, 0).directions.add(direction.begin);

			for(int j=1;j<str1.length()+1;j++){
				if (opt_table.containsKey(mapping_2To1(i, j)))
				{
					sub_mapping(i, j).value=0;
					sub_mapping(i, j).directions.add(direction.begin);
					continue;
				}

				int l_value=0,u_value=0;
				if (utils.Constant.isAffineGapScore){
					l_value = sub_mapping(i, j-1).value + (useGapExtensionOnThisElement(i, j, direction.left)? utils.Constant.extend : utils.Constant.indel);
					u_value = sub_mapping(i-1, j).value + (useGapExtensionOnThisElement(i, j, direction.up)? utils.Constant.extend : utils.Constant.indel);
				}
				else{
					l_value=sub_mapping(i,j-1).value + utils.Constant.indel;
					u_value=sub_mapping(i-1, j).value + utils.Constant.indel;
				}
				int d_value=sub_mapping(i-1, j-1).value + matchOrNot(i, j);
				int zero_value=0;

				entry e;
				if (utils.Constant.isAffineGapScore){
					e = maxWithAffine(new entry(direction.left, l_value),new entry(direction.up, u_value),
							new entry(direction.diagonal,d_value), new entry(direction.begin, zero_value));
				}
				else
				{
					e = maxWithoutAffine(new entry(direction.left, l_value),new entry(direction.up, u_value),
							new entry(direction.diagonal,d_value), new entry(direction.begin, zero_value));
				}

				sub_mapping(i, j) .directions = e.directions;
				sub_mapping(i, j) .value = e.value;
			}
		}
	}

	boolean useGapExtensionOnThisElement(int x,int y, direction d){
		if (d==direction.up){
			if (x-2<0)
				return false;
			else
			{
				if (opt_mapping(x-2, y).value - opt_mapping(x-1, y).value == (-1)*utils.Constant.indel)
					return true;
				else if (opt_mapping(x-2, y).value - opt_mapping(x-1, y).value == (-1)*utils.Constant.extend)
					return true;
				else
					return false;
			}
		}
		else if (d==direction.left){
			if (y-2 <0)
				return false;
			else{
				if (opt_mapping(x, y-2).value - opt_mapping(x, y-1).value == (-1)*utils.Constant.indel)
					return true;
				else if (opt_mapping(x, y-2).value - opt_mapping(x, y-1).value == (-1)*utils.Constant.extend)
					return true;
				else
					return false;
			}
		}
		else
			return false;
	}

	private entry sub_mapping(int x, int y) {
		return sub_matrix.get(x*(str1.length()+1)+y);
	}

	public void sub_backtrack(){
		sub_alignments = new ArrayList<List>();
		sub_alignments_str1 = new ArrayList<String>();
		sub_alignments_str2 = new ArrayList<String>();
		for(int i=str2.length();i>0;i--){
			for(int j=str1.length();j>0;j--){
				if (sub_table.containsKey(mapping_2To1(i, j))){
					continue;
				}

				if (sub_mapping(i, j).value >=getThreshhold()){
					suboptimalResult(i,j);
				}
			}
		}
	}

	void suboptimalResult(int x, int y) {
		for(direction d:sub_mapping(x, y).directions){
			switch (d){

			case diagonal:
				if (	utils.Constant.isAffineGapScore
						&& (
								(x+1<str2.length()+1 && useGapExtensionOnThisElement(x+1, y, direction.up)) 
								||  (y+1<str1.length()+1 && useGapExtensionOnThisElement(x, y+1, direction.left))
								)
						)
					break;
				else
				{				
					sub_tmplist.add(mapping_2To1(x, y));
					if(str1.charAt(y-1) == str2.charAt(x-1))
					{
						sub_tmp_str1 = String.valueOf(str1.charAt(y-1)).toLowerCase() + sub_tmp_str1;
						sub_tmp_str2 = String.valueOf(str2.charAt(x-1)).toLowerCase() + sub_tmp_str2;
					}
					else
					{
						sub_tmp_str1 = String.valueOf(str1.charAt(y-1)).toUpperCase() + sub_tmp_str1;
						sub_tmp_str2 = String.valueOf(str2.charAt(x-1)).toUpperCase() + sub_tmp_str2;
					}
					suboptimalResult(x-1, y-1);
					sub_tmplist.remove(sub_tmplist.size()-1);
					sub_tmp_str1 = sub_tmp_str1.substring(1);
					sub_tmp_str2 = sub_tmp_str2.substring(1);
					
				}
				break;

			case left:
				sub_tmplist.add(mapping_2To1(x, y));
				sub_tmp_str1 = String.valueOf(str1.charAt(y-1)).toUpperCase() + sub_tmp_str1;
				sub_tmp_str2 = sign_indel + sub_tmp_str2;
				suboptimalResult(x, y-1);
				sub_tmplist.remove(sub_tmplist.size()-1);
				sub_tmp_str1 = sub_tmp_str1.substring(1);
				sub_tmp_str2 = sub_tmp_str2.substring(1);
				break;
			case up:
				sub_tmplist.add(mapping_2To1(x, y));
				sub_tmp_str1 = sign_indel + sub_tmp_str1;
				sub_tmp_str2 = String.valueOf(str2.charAt(x-1)).toUpperCase() + sub_tmp_str2;
				suboptimalResult(x-1, y);
				sub_tmplist.remove(sub_tmplist.size()-1);
				sub_tmp_str1 = sub_tmp_str1.substring(1);
				sub_tmp_str2 = sub_tmp_str2.substring(1);
				break;
			case begin:
				ArrayList<Integer> sub_alignment = new ArrayList<Integer>(sub_tmplist);
				sub_alignments.add(sub_alignment);
				sub_alignments_str1.add(new String(sub_tmp_str1));
				sub_alignments_str2.add(new String(sub_tmp_str2));
				for(int i:sub_alignment){
					if (sub_table.containsKey(i)){
						((ArrayList<Integer>) sub_table.get(i)).add(sub_alignments.size()-1);
					}
					else
					{
						ArrayList<Integer>	tmp = new ArrayList<Integer>();
						tmp.add(sub_alignments.size()-1);
						sub_table.put(i, tmp);
					}
				}

				return;
			}
		}
	}

	//************************************************************************************************
	//************************************************************************************************
	//optimal
	//************************************************************************************************
	//************************************************************************************************
	public void showResult(){
		backtracking();

	}
	public void backtracking(){
		opt_alignments = new ArrayList<List>();
		opt_alignments_str1 = new ArrayList<String>();
		opt_alignments_str2 = new ArrayList<String>();
		sub_alignments.clear();
		sub_alignments_str1.clear();
		sub_alignments_str2.clear();
		for (int i=str2.length();i>0;i--){
			for(int j=str1.length();j>0;j--){
				//				if (opt_table.containsKey(mapping_2To1(i, j))){
				//					continue;
				//				}
				if (opt_mapping(i, j).value ==largest){
					//optimalResult_stack(i,j);
					optimalResult(i, j);
				}
			}
		}
	}
	//************************************************************************************************
	//************************************************************************************************
	//print
	//************************************************************************************************
	//************************************************************************************************
	public void printMatrix(){
		for(int i=0;i<str2.length()+1;i++){
			for(int j=0;j<str1.length()+1;j++){
				System.out.print(opt_mapping(i, j).value+ "  ");
				//f.
			}
			System.out.println();
		}
	}

	public void printSubMatrix(){
		for(int i=0;i<str2.length()+1;i++){
			for(int j=0;j<str1.length()+1;j++){
				System.out.print(sub_matrix.get(mapping_2To1(i, j)).value+ "  ");
			}
			System.out.println();
		}
	}

	public void printHashtable(){
		Enumeration v=opt_table.keys();

		while(v.hasMoreElements()){
			int i = (Integer) v.nextElement();
			int[] tmp=mapping_1To2(i);
			System.out.print(tmp[0]+" "+tmp[1]+":  ");

			ArrayList<Integer> value = (ArrayList<Integer>) opt_table.get(i);
			for(int vi:value){
				System.out.print(vi+"  ");
			}
			System.out.println();
		}
	}

	public void printSubHashtable(){
		Enumeration v=sub_table.keys();

		while(v.hasMoreElements()){
			int i = (Integer) v.nextElement();
			int[] tmp=mapping_1To2(i);
			System.out.print(tmp[0]+" "+tmp[1]+":  ");

			ArrayList<Integer> value = (ArrayList<Integer>) sub_table.get(i);
			for(int vi:value){
				System.out.print(vi+"  ");
			}
			System.out.println();
		}

	}
	//************************************************************************************************
	//************************************************************************************************
	//************************************************************************************************
	//************************************************************************************************

	public int mapping_2To1(int x, int y){
		return x*(str1.length()+1)+y;
	}

	public int[] mapping_1To2(int x){
		int s1=str1.length()+1;
		int j = x%s1;
		int i = x/s1;
		return new int[]{i,j};
	}
	//************************************************************************************************
	//************************************************************************************************
	//optimal
	//************************************************************************************************
	//************************************************************************************************

	void optimalResult(int x,int y){
		for(direction d:opt_mapping(x, y).directions){
			switch (d){

			case diagonal:
//				if (	utils.Constant.isAffineGapScore &&
//						(
//								(x+1<str2.length()+1 && useGapExtensionOnThisElement(x+1, y, direction.up)) 
//								||  (y+1<str1.length()+1 && useGapExtensionOnThisElement(x, y+1, direction.left))
//								)
//						)
//					break;
				if(		utils.Constant.isAffineGapScore &&
						(
						(	opt_mapping(x, y).directions.contains(direction.left) && opt_mapping(x, y-1).directions.contains(direction.left)	)
						|| (	opt_mapping(x, y).directions.contains(direction.up) && opt_mapping(x-1, y).directions.contains(direction.up)	)
						)
					)
				{
						break;
				}
				else
				{
					opt_tmplist.add(mapping_2To1(x, y));
					if(str1.charAt(y-1)==str2.charAt(x-1))
					{
						opt_tmp_str1 = String.valueOf(str1.charAt(y-1)).toLowerCase() + opt_tmp_str1;
						opt_tmp_str2 = String.valueOf(str2.charAt(x-1)).toLowerCase() + opt_tmp_str2;
					}
					else
					{
						opt_tmp_str1 = String.valueOf(str1.charAt(y-1)).toUpperCase() + opt_tmp_str1;
						opt_tmp_str2 = String.valueOf(str2.charAt(x-1)).toUpperCase() + opt_tmp_str2;
					}
					optimalResult(x-1, y-1);
					opt_tmplist.remove(opt_tmplist.size()-1);
					opt_tmp_str1 = opt_tmp_str1.substring(1);
					opt_tmp_str2 = opt_tmp_str2.substring(1);
				}
				break;

			case left:			
				opt_tmplist.add(mapping_2To1(x, y));
				opt_tmp_str1 = String.valueOf(str1.charAt(y-1)).toUpperCase() + opt_tmp_str1;
				opt_tmp_str2 = sign_indel + opt_tmp_str2;
				optimalResult(x, y-1);		
				opt_tmplist.remove(opt_tmplist.size()-1);
				opt_tmp_str1 = opt_tmp_str1.substring(1);
				opt_tmp_str2 = opt_tmp_str2.substring(1);

				break;
			case up:				
				opt_tmplist.add(mapping_2To1(x, y));
				opt_tmp_str1 = sign_indel + opt_tmp_str1;
				opt_tmp_str2 = String.valueOf(str2.charAt(x-1)).toUpperCase() + opt_tmp_str2;
				optimalResult(x-1, y);
				opt_tmplist.remove(opt_tmplist.size()-1);
				opt_tmp_str1 = opt_tmp_str1.substring(1);
				opt_tmp_str2 = opt_tmp_str2.substring(1);

				break;
			case begin:
				ArrayList<Integer> opt_alignment = new ArrayList<Integer>(opt_tmplist);
				opt_alignments.add(opt_alignment);
				opt_alignments_str1.add(new String(opt_tmp_str1));
				opt_alignments_str2.add(new String(opt_tmp_str2));
				for(int i:opt_alignment){
					//opt_table.put(i, opt_alignments.size()-1);
					if (opt_table.containsKey(i))
					{
						((ArrayList<Integer>)opt_table.get(i)).add(opt_alignments.size()-1);
					}
					else
					{
						ArrayList<Integer> tmp = new ArrayList<Integer>();
						tmp.add(opt_alignments.size()-1);
						opt_table.put(i, tmp);
					}
				}

				return;
			}
		}
	}

	public ArrayList<String> getOpt_alignments_str1() {
		return opt_alignments_str1;
	}
	public ArrayList<String> getOpt_alignments_str2() {
		return opt_alignments_str2;
	}
	public ArrayList<String> getSub_alignments_str1() {
		return sub_alignments_str1;
	}
	public ArrayList<String> getSub_alignments_str2() {
		return sub_alignments_str2;
	}
	void optimalResult_stack(int x,int y){
		Stack s = new Stack();
		int key = mapping_2To1(x, y);
		s.push(new int[]{key,0});
		opt_tmplist.add(key);

		while(!s.empty()){
			int[] top = (int[]) s.peek();

			if (top[1] < opt_matrix.get(top[0]).directions.size())
			{
				direction d = opt_matrix.get(top[0]).directions.get(top[1]);
				top[1]++;
				s.pop();
				s.push(top);
				int nextkey;
				switch (d){
				case diagonal:
					nextkey = top[0] - 1 - getStr1().length() - 1;
					s.push(new int[]{nextkey , 0});
					opt_tmplist.add(nextkey);
					break;
				case left:
					nextkey = top[0] - 1;
					s.push(new int[]{nextkey , 0});
					opt_tmplist.add(nextkey);
					break;
				case up:
					nextkey = top[0] - 1 - getStr1().length();
					s.push(new int[]{nextkey , 0});
					opt_tmplist.add(nextkey);
					break;
				case begin:
					ArrayList<Integer> opt_alignment = new ArrayList<Integer>(opt_tmplist);
					opt_alignment.remove(opt_alignment.size()-1);
					opt_alignments.add(opt_alignment);
					for(int i:opt_alignment){
						//opt_table.put(i, opt_alignments.size()-1);
						if (opt_table.containsKey(i))
						{
							((ArrayList<Integer>)opt_table.get(i)).add(opt_alignments.size()-1);
						}
						else
						{
							ArrayList<Integer> tmp = new ArrayList<Integer>();
							tmp.add(opt_alignments.size()-1);
							opt_table.put(i, tmp);
						}
					}

				}
			}
			else{
				s.pop();
				opt_tmplist.remove(opt_tmplist.size()-1);
			}

		}

	}


	//************************************************************************************************
	//************************************************************************************************
	//scoring
	//************************************************************************************************
	//************************************************************************************************
	private int matchOrNot(int i, int j){
		if (str1.charAt(j-1)==str2.charAt(i-1))
			return utils.Constant.match;
		else 
			return utils.Constant.mismatch;
	}
	//************************************************************************************************
	//************************************************************************************************
	//optimal
	//************************************************************************************************
	//************************************************************************************************
	private entry opt_mapping(int x,int y){
		return opt_matrix.get(x*(str1.length()+1)+y);
	}
	//************************************************************************************************
	//************************************************************************************************
	//computing
	//************************************************************************************************
	//************************************************************************************************
	private entry maxWithAffine(entry l,entry u, entry d, entry z){
		entry max = z;

		if (max.value == d.value){
			max.directions.add(d.directions.get(0));

		}
		else if (max.value < d.value){
			max = d;
		}

		if (max.value == l.value){
			max.directions.add(l.directions.get(0));
		}
		else if (max.value < l.value){
			max = l;
		}

		if (max.value == u.value){
			max.directions.add(u.directions.get(0));
		}
		else if (max.value < u.value){
			max = u;
		}

		return max;
	}

	private entry maxWithoutAffine(entry l,entry u, entry d, entry z){
		entry max = z;

		if (max.value == d.value){
			max.directions.add(d.directions.get(0));

		}
		else if (max.value < d.value){
			max = d;
		}

		//	if (max.value == l.value){
		//		max.directions.add(l.directions.get(0));
		//
		//	}
		//	else 
		if (max.value < l.value){
			max = l;
		}

		//	if (max.value == u.value){
		//		max.directions.add(u.directions.get(0));
		//
		//	}
		//	else 
		if (max.value < u.value){
			max = u;
		}

		return max;
	}


	enum direction{
		left,
		up,
		diagonal,
		begin
	}


	class entry{
		List<direction> directions=new ArrayList<LocalAlignment.direction>();
		int value;

		public entry(direction d, int value){
			directions.add(d);
			this.value=value;
		}
		public entry(){

		}
	}





}
